Національний університет “Львівська політехніка” Кафедра ЕОМ Курсова робота ( частина 2 ) На тему: “ Динамічні структури даних ” з дисципліни: " Програмування" Вибір варіантів індивідуального завдання: Вибір АТД: № Варіанту = (2 + 1994 + 111) % 4 + 1 = 4. Примітка: 1 – стек, 2 – черга, 3- список, 4 – дерево. Вибір номера завдання: № Варіанту = 2  Зміст 2. Завдання 2: Динамічні структури даних 3 2.1. Теоретична частина 3 2.2. Частина 1. Побудова АТД 4 2.2.1. Постановка задачі 4 2.2.2. Динаміка вмісту 4 2.2.3. Результати виконання програми 5 2.3. Частина 2. Застосування АТД 6 2.3.1. Постановка задачі 6 2.3.2. Алгоритм розв’язання задачі 6 2.3.3. Результати виконання програми 7 Висновки 8 Список літератури 9 Додатки 10  2. Завдання 2: Динамічні структури даних 2.1 Теоретична частина Переваги динамічних структур даних Динамічні структури даних щодо визначення характеризуються відсутністю фізичної суміжності елементів структури пам'яті непостійністю і непередбачуваністю розміру (числа елементов4) структури в процесі її обробки. У цьому розділі розглянуто особливості динамічних структур, що визначаються їх першим характерним властивістю. Оскільки елементи динамічної структури розташовуються по непередбачуваним адресами пам'яті, адреса елемента такої структури не може бути обчислений з адреси початкового або попереднього елемента. Для встановлення зв'язку між елементами динамічної структури використовуються покажчики, через які встановлюються явні зв'язки між елементами. Таке подання даних у пам'яті називається зв'язковим. Елемент динамічної структури складається з двох полів: інформаційного поля або поля даних, в якому містяться ті дані, заради яких і створюється структура; в загальному випадку інформаційне поле саме є інтегрованою структурою-вектором, масивом, записом і т.п.; полі зв'язок, в якому містяться один або кілька покажчиків, що зв'язує цей елемент з іншими елементами структури. Коли зв'язне подання даних використовується для розв'язання прикладної задачі, для кінцевого користувача дивись робиться тільки вміст інформаційного поля, а поле зв'язок використовується тільки програмістом-розробником. Переваги зв'язкового представлення даних: у можливості забезпечення значної мінливості структур; розмір структури обмежується тільки розміром пам'яті машини; при зміні логічної послідовності елементів структури потрібно не переміщення даних в пам'яті, а тільки корекція покажчиків. Однак існують і недоліки: робота з покажчиками вимагає, як правило, більш високої кваліфікації від програміста; на поля зв'язок витрачається додаткова пам'ять; доступ до елементів зв'язного структури може бути менш ефективним за часом. Застосування динамічних структур Останній недолік є найбільш серйозним і саме їм обмежується застосовність зв'язкового представлення даних. Якщо в суміжному поданні даних для обчислення адреси будь-якого елемента нам у всіх випадках достатньо було номера елемента або інформації, що міститься в дескрипторі структури, то для зв'язкового подання адресу елемента не може бути обчислений з вихідних даних. Дескриптор зв'язного структури містить один або кілька покажчиків, що дозволяють увійти в структуру, далі пошук і необхідного елемента виконується проходженням по ланцюжку покажчиків від елемента до елементу. Тому зв'язне уявлення практично ніколи не застосовується в задачах, де логічна структура даних має вигляд вектора або масиву - з доступом за номером елемента, але часто застосовується в задачах, де логічна структура вимагає іншої вихідної інформації доступу (таблиці, стеки, списки, дерева і т . д.). Дерево - в інформатиці та програмуванні одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з одного або більше вузлів (nodes), яка задовольняє наступним вимогам: існує один відокремлений вузол - корень (root) дерева інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множин T1, ..., Tm і кожна з цих множин в свою ...